#include "../include/header.h"

bool verifySquenceOfBST(int squence[], int length)
{
    if(squence == NULL || length <= 0)
        return false;

    // root of a BST is at the end of post order traversal squence
    int root = squence[length - 1];

    // the nodes in left sub-tree are less than the root
    int i = 0;
    for(; i < length - 1; ++ i) {
        if(squence[i] > root)
            break;
    }

    // the nodes in the right sub-tree are greater than the root
    int j = i;
    for(; j < length - 1; ++ j) {
        if(squence[j] < root)
            return false;
    }

    // verify whether the left sub-tree is a BST
    bool left = true;
    if(i > 0)
        left = verifySquenceOfBST(squence, i);

    // verify whether the right sub-tree is a BST
    bool right = true;
    if(i < length - 1)
        right = verifySquenceOfBST(squence + i, length - i - 1);

    return (left && right);
}

bool Adjuge(int *a, int low, int high)
{
    if (low == high)
        return true;

    int i = high - 1;
    while (a[i] > a[high] && i >= low) i--;

    if (!Adjuge(a, i + 1, high - 1))
        return false;

    int k = i;
    while (a[i] < a[high] && i >= low) i--;

    return Adjuge(a, low, k);

}

#define SIZE 7
void TestForNine()
{
    int  a[SIZE];

    cout << "Please input " << SIZE << "numbers into the array:" << endl;

    for (int i = 0; i < SIZE; i++)
        cin >> a[i];

    bool flag = verifySquenceOfBST(a, SIZE);
    if (flag)
        cout << "It's  a last rules scan" <<endl;
    else
        cout << "It isn't a last rules scan" <<endl;

}
